package com.example.recall31;

/**
 * @description 八皇后，每个棋子所在的行、列、对角线都不能有另外一个棋子
 * @auther lijiewei
 * @date 2022/2/9 14:34
 */
public class EightQueens {

    //下标表示行，值表示哪一列
    private int[] result = new int[8];

    /**
     * 处理第 row 行，放置棋子在哪一列
     * @param row 行序号
     * @return
     * @author lijiewei
     * @date   2022/2/9 14:44
     */
    public void cal8queens(int row) {
        //8 个棋子都被放置好了，不再递归，打印结果
        if (row == 8) {
            printQueens(result);
            return;
        }
        //每一行依次判断8列中哪一列可以放
        for (int column = 0; column < 8; column++) {
            //判断是否可以放
            if (isOk(row, column)) {
                //第row  行的棋子放在 column 列
                result[row] = column;
                //安放下一行
                cal8queens(row+1);
            }
        }
    }

    /**
     * 第 row 行第 column 列是否可以安放棋子
     * @param row 第 row 行
     * @param column 第 column 列
     * @return
     * @author lijiewei
     * @date   2022/2/9 15:00
     */
    private boolean isOk(int row, int column) {
        //左上列
        int leftup = column - 1;
        //右上列
        int rightup = column + 1;

        //逐行往上考察每一行
        for (int i = row-1; i >= 0; i--) {
            //第 i 行第 column 列是否有棋子
            if (result[i] == column) {
                return false;
            }
            //左上对角线，第 i 行 leftup 列是否有棋子
            if (leftup >= 0) {
                if (result[i] == leftup) {
                    return false;
                }
            }
            //右上角对角线，第 i 行 rightup 列是否有棋子
            if (rightup < 8) {
                if (result[i] == rightup) {
                    return false;
                }
            }
            leftup--;
            rightup++;
        }
        return true;
    }

    /**
     * 打印安放棋子的二维矩阵
     * @param result 每行棋子放的位置
     * @return
     * @author lijiewei
     * @date   2022/2/9 14:50
     */
    private void printQueens(int[] result) {
        for (int row = 0; row < 8; row++) {
            for (int column = 0; column < 8; column++) {
                if (result[row] == column) {
                    System.out.print("Q ");
                } else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }


}
